package com.jerry.base.java8.hiorder;

import java.util.LinkedList;

/**
 * 高阶函数-二叉树
 *
 * @author Jerry
 * @since 2024/8/1 21:48
 */
public class BinaryTree {

    public record TreeNode(int value, TreeNode left, TreeNode right) {
        @Override
        public String toString() {
            return "%d ".formatted(value);
        }
    }

    public static void traverse(TreeNode root) {
        // 用来记住回去的路
        LinkedList<TreeNode> stack = new LinkedList<>();
        // 当前节点
        TreeNode curr = root;
        // 记灵最近一次处理完的节点
        TreeNode last = null;
        // 没有向左走到头或者还有未归的路
        while (curr != null || !stack.isEmpty()) {
            // 左边未走完
            if (curr != null) {
                // 记住来时的路
                stack.push(curr);
                // TODO 处理前序遍历的值
                // 下次向左走
                curr = curr.left;
            }
            // 左边已走完
            else {
                // 上次的路
                TreeNode peek = stack.peek();
                // 没有右子树
                if (peek.right == null) {
                    // TODO 处理中序、后序遍历的值
                    last = stack.pop();
                }
                // 有右子树，己走完
                else if (peek.right == last) {
                    // TODO 处理后序遍历的值
                    last = stack.pop();
                }
                // 有右子树，未定完
                else {
                    // TODO 处理中序后序遍历的值
                    // 下次向右走
                    curr = peek.right;
                }
            }
        }
    }

    /*
        1
       / \
      2   3
     /   / \
    4   5   6
    前序：1 2 4 3 5 6 值左右
    中序：4 2 1 5 3 6 左值右
    后序：4 2 5 6 3 1 左右值
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4, null, null),
                        null),
                new TreeNode(3,
                        new TreeNode(5, new TreeNode(6, null, null),
                                null), null));
        traverse(root);
    }
}
